Modulo 3 generation finds application in the field of arithmetic error codes utilization and more particularly in the area of residue code generation. An arithmetic error code is a redundant representation of numbers having the property that certain errors can be detected or corrected in arithmetic operations. A residue code is a separate arithmetic code, in which the information to be used in checking, called check code, is attached to the representation of the number; that is, the number and its check code are processed separately. The check code is attached to the number, say N, is the residue modulo m of that number; that is, the remainder in the division of N by m.
Mathematically speaking, every number N can be represented as a set of two numbers, called codeword
&lt;N, rm(N)&gt;,
where N is any integer, and rm(N) is the remainder of N/m. Addition and multiplication of N1 and N2 are defined as follows: EQU &lt;N1, rm(N1)&gt;+&lt;N2, rm(N2)&gt;=&lt;N1+N2, rm(N1) + rm(N2)&gt; (1)
and EQU &lt;N1, rm(N1)&gt;.multidot.&lt;N2, rm(N2)&gt;=&lt;N1.multidot.N2, rm(N1) .multidot. rm(N2)&gt; (2)
where + and .multidot. are addition and multiplication modulo m. Furthermore, if the equations EQU rm(N1+N2)=rm(N1) + rm(N2) (3)
and EQU rm(N1.multidot.N2)=rm(N1) .multidot. rm(N2) (4)
are satisfied, then the sum or product of any two code words yields another codeword. This property is called code closure under addition and multiplication respectively. The error checking circuit simply checks whether the sum or product is another code word.
Consider a k-bit binary number N, wherein ##EQU1## Using Equations (3) and (4), we can find modulus of N ##EQU2## where .SIGMA. is modulo-sum symbol. Note that for all n.sub.i .epsilon.{0, 1}, r.sub.m (n.sub.i)=n.sub.i, if m&gt;1 and n.sub.i .multidot. k=n.sub.i .multidot.k. Therefore, ##EQU3## Furthermore, using (4) for all integers i, i.gtoreq.0 ##EQU4## Thus, modulo 3 of a number can be performed by adding number of 1's and 2's in modulo 3 fashion. Therefore, modulo three is suitable for use in arithmetic error code applications.
In a high speed data processing system it is important that the residue checking operation be performed quickly so as not to incur a delay in the overall arithmetic operation. One high speed method of modulo generation involves the use of read-only memories (ROM's) wherein a ROM is "addressed" by a number and the desired modulo of that number is read out therefrom, see for example U.S. Pat. No. 3,980,874 issued Sept. 14, 1976 for "BINARY TO MODULO M TRANSLATION". However, the cost of ROM implementation for modulo translation can become rather excessive particularly for modulo translation of very large numbers. Another alternative is to design a particular modulo generator for each particular applicaion. However, the inflexability of this approach renders it less than desirable for many applications. The need exists for an inexpensive, reliable, flexible modulo generator, particularly a modulo 3 generator for residue code generation.